Teoría de Grafos

La Teoría de grafos es parte de la Matemática Discreta y se relaciona con las áreas de investigación operativa y optimización combinatoria. Muchos problemas que surgen en la actualidad, son problemas "difíciles"(NP-completos, NP-Hard) de resolver. Es por esto que constantemente surgen requerimientos desde la sociedad para desarrollar nuevos modelos, teorías y algoritmos para satisfacer esta demanda. Los grafos son estructuras combinatorias muy simples pero son también herramientas muy poderosas que sirven para modelar una gran variedad de problemas en diversas disciplinas. Existen varias maneras de abordar estos problemas. Una forma de resolverlos de forma exacta y técnicas de optimización combinatoria. Lamentablemente, estos algoritmos siguen siendo de complejidad exponencial y resultan inútiles para resolver instancias aún mayores. En cambio, se presenta la posibilidad es tratar de determinar si el grafo en cuestión pertenece a alguna clase conocida de grafos tal que el problema en consideración resulta ser polinomial para esta clase.

Este grupo de investigación se dedica, en pocas palabras, a estudiar ciertas clases de grafos que modelan problemas específicos y algunas veces a resolver ciertos problemas en dichas clases.

Clases estudiadas:

Grafos Cordales y sus subclases
Grafos Dualmente cordales y sus subclases
Grafos de intersección de caminos en una grilla
Grafos de contención de caminos de un árbol
Grafos Dirigidos
Grafos Distancia Regularizados
Problemas estudiados:
Corte máximo
Pebbling
Convexidad

Publicaciones

- Strong cliques and equistability of EPT graphs, L. Alcón, M. Gutierrez, I. Kovacs, M. Milanic, R. Rizzi, Discrete Applied Mathematics, Vol. 203, pp. 13-25, (2016).
- A note on path domination, L. Alcón, Discussiones Mathematicae Graph Theory, Vol. 36, pp. 1021–1034, ( 2016).2019
- Vertex intersection graphs of paths on a grid: characterization within block graphs, L. Alcón, F. Bonomo, M.P. Mazzoleni, Graphs and Combinatorics, Vol. 33, número 4, pp. 653-664, (2017).
- Pebbling in semi-2-trees, L. Alcón, G. Hurlbert, M. Gutierrez,Discrete Mathematics, Volume 340, Issue 7, ( 2017), Pages 1467–1480.
- Helly EPT graphs on bounded degree trees: forbidden induced subgraphs and efficient recognition, L. Alcón, M. Gutierrez, M.P. Mazzoleni, Discrete Mathematics 340 (2017) pp. 2798-2806.
- On basic chordal graphs and some of its subclasses, Pablo De Caria y Marisa Gutierrez, Discrete Applied Mathematics 210 (2016), 261-276.
- On models of directed path non rooted directed path graph, M. Gutierrez (UNLP), S. Tondato (UNLP), Graphs and Combinatorics 32, 2, pp 663-684 (2016).
- End simplicial vertices in path graphs. M. Gutierrez (UNLP), S. Tondato (UNLP), Discussiones Mathematicae Graph Theory 36, pág 393–408 (2016) .
- On rooted directed path graphs, M. Gutierrez (UNLP), S. Tondato (UNLP) Revista de la UMA Vol. 57 Nro 1, pág. 111-144 (2016).
- Extended star graph, M. Gutierrez (UNLP), S. Tondato (UNLP), Algebra and Discrete Mathematics Volume 21 (2016). Number 2, pp. 239–254 Journal Algebra and Discrete Mathematics.
- On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid, L. Alcón, F. Bonomo, G. Durán, M. Gutierrez, M.P. Mazzoleni, B. Ries, M. Valencia, Discrete Applied Mathematic, Vol. 234, pp 12-21 Elsevier.
- Recent results on containment graphs of paths in trees, L. Alcón, N. Gudiño, M. Gutierrez, Discrete Applied Mathematics, vol. 245, pp 139-147. Elsevier
- End vertices in interval containment graphs, L. Alcón, N. Gudiño y M. Gutierrez. Matematica Contemporânea, 45, pp86-96, Sociedad Brasileira de Matemática.
- On clique-inverse graphs of graphs with bounded clique number, L. Alcón, S. Gravier, C. Linhares Sales, F. Protti, G. Ravenna, Journal of Graph Theory, Volumen 94, issue 4, pp. 531-538.
- Proper circular arc graphs as intersection graphs of paths on a grid.Autores: Esther Galby, María Pía Mazzoleni, Bernard Ries. Discrete Applied Mathematics. Año: 2019.Volume: 262.Pages: 195-202.
- On some special classes of contact B0-VPG graphs. Autores: Flavia Bonomo, María Pía Mazzoleni, Mariano Leonardo Rean, Bernard Ries. Discrete Applied Mathematics. (En Prensa) Año: 2019.
- Characterising chordal contact B0-VPG graphs. Flavia Bonomo, María Pía Mazzoleni, Mariano Leonardo Rean, Bernard Ries. Lecture Notes in Computer Science. Año: 2018. Volumen: 10856. Pages 89–100.
- Families of induced trees and their intersection graphs, Pablo De Caria, Electronic Notes in Theoretical Computer Science 346 (2019) 265-274.9
- Neighborhood inclusion posets and tree representations for chordal and dually chordal graphs, Pablo De Caria, Discrete Applied Mathematics 281 (2020), 151- 161. (Publicado en prensa en 2019).

Resumenes extendidos publicados en proceedings de congresos:

- On the Existence of Critical Clique-Helly Graphs, L. Alcón, M.Pizaña, G. Ravenna, Electronic Notes in Discrete Mathematics, Volume 62, Paginas 231- 236, (2017).
- A characterization of claw-free CIS graphs and new results on the order of CIS graphs, L. Alcon, M Gutierrez, M. Milanic, Electronic notes in Theoretical Computer Science, Volume 346, 30 August 2019, Pages 15-27.
- On the recognition of neighborhood inclusion posets, Pablo De Caria, Electronic Notes in Discrete Mathematics 62 (2017) 285-290. t-Pebbling for k-connected graphs with a universal vertex, L. Alcón, M. Gutierrez, G. Hurlbert, Matemática contemporanea., Volumen 46 (2020), pp 38-46.
- Two infinite families of critical clique-Helly graphs, L. Alcón, M. Pizaña, G. Ravenna, Discrete Applied Mathematics, Volume 281, 15, pp. 2-5., 2020.
- On k-tree containment graphs of paths in a tree, L. Alcón, N. Gudiño y M. Gutierrez, aceptado en Order, Febrero 2020.

Integrantes y contactos